package puzzle.puzzleup2008;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import astudy.util.AdvMath;

/**
 * A 6 digit lottery ticket hits the jackpot. 
 * Tickets whose numbers differ from the winning 
 * ticket with only one digit (54 tickets) get 
 * consolation prizes. 
 * 
 * The jackpot winning number is a prime, and none 
 * of the consolation prize winners is a prime number. 
 * What is the largest "winning number" that satisfies 
 * these conditions ?
 * 
 * @author wong tong
 *
 */
public class LotteryTicket {

	public static void main(String[] args) {
		
		//search for all prime numbers
		Map<String, Boolean> map = new HashMap<String, Boolean>();
		for (int i = 0; i < 1000000; i ++) {
			if (AdvMath.isPrime(i)) {
				String t = String.valueOf(i);
				while (t.length() < 6) {
					t = "0"+t;
				}
				map.put(t, true);
			}
		}
		//test
		List<String> array = new ArrayList<String>();
		for (String t: map.keySet()) {
			if (check(map, t)) {
				array.add(t);
			}
		}
		System.out.println(array);
	}

	private static List<String> getConsolationPrizeNumber(String t) {
		//create 54 consolation prize
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < 6; i ++) {
			String prefix = t.substring(0, i);
			String suffix = t.substring(i+1);
			int c = t.charAt(i)-'0';
			for (int j = 0; j < 10; j ++) {
				if (j != c) {
					list.add(prefix + String.valueOf(j) + suffix);
				}
			}
		}
		return list;
	}
	
	private static boolean check(Map<String, Boolean> map, String t) {
		
		List<String> list = getConsolationPrizeNumber(t);
		for (String s: list) {
			if (map.get(s) != null) {
				return false;
			}
		}
		return true;
	}
}
